package com.hyper_yang.algorithmRecord;

// leetcode 45 跳跃游戏 II
public class LeetCode_45 {
    /*
        给定一个长度为 n的 0索引整数数组 nums。初始位置为 nums[0]。
        每个元素 nums[i]表示从索引 i向后跳转的最大长度。
        换句话说，如果你在 nums[i]处，你可以跳转到任意 nums[i + j]处:
        0 <= j <= nums[i]
        i + j < n
        返回到达 nums[n - 1]的【最小跳跃次数】。生成的测试用例可以到达 nums[n - 1]。
     */
    // 方法一: 反向跳跃 【结果至少是最少之一】 【无后效性才用贪心】
    public static int jump1(int[] nums) {
        // 保存跳跃步数
        int step = 0;
        // 定义循环变量
        int currPos = nums.length - 1;
        // 不停的向前跳跃，以最远的距离
        while (currPos > 0) {
            // 从前往后遍历数组元素，找到当前距离最远的 "上一步位置 "
            for (int i = 0; i < currPos; i++) {
                if (i + nums[i] >= currPos) {
                    currPos = i; // 从前到后，第一次能跳到当前位置的位置，就是最远的上一步位置
                    step++;
                    break;
                }
            }
        }
        return step;
    }

    // 方法二: 正向跳跃
    public static int jump2(int[] nums) {
        int steps = 0;
        int currPos = 0;

        int farthest = 0, nextFarthest = farthest;
        // 寻找下一步合适位置
        while (farthest < nums.length - 1) {
            // 遍历 currPos - farthest范围内的所有元素，选择第二步跳跃最远的作为当前一步的选择
            for (int i = currPos; i <= farthest; i++) {
                if (i + nums[i] > nextFarthest) {
                    nextFarthest = i + nums[i];
                    currPos = i;
                }
            }
            steps++;
            farthest = nextFarthest;
        }
        return steps;
    }

    // 改进:
    public static int jump(int[] nums) {
        int steps = 0;

        int farthest = 0, nextFarthest = farthest;

        for (int i = 0; i < nums.length - 1; i++) {
            if (i + nums[i] > nextFarthest) {
                nextFarthest = i + nums[i];
            }
            if (i == farthest) {
                steps++;
                farthest = nextFarthest;
            }
        }
        return steps;
    }

    public static void main(String[] args) {
        System.out.println(jump(new int[]{2, 3, 1, 1, 4})); // 2
        System.out.println(jump(new int[]{2, 3, 0, 1, 4})); // 2
    }
}
